{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm design and anlysis-2025 spring  homework 2\n",
    "**Deadline**：2025.5.14\n",
    "\n",
    "**name**:\n",
    "\n",
    "\n",
    "note：\n",
    "---\n",
    "1. 带有\\*的题目，申请免上课的同学，必须完成，其他同学选作；\n",
    "2. 请独立完成，如求助了他人或者大模型，请著明，并且不可省略算法分析部分；\n",
    "4. 如若作答有雷同，全部取消成绩；\n",
    "3. 需要书面作答的题目，可以通过引用图片的形式添加，但是注意上传项目时包含所引用的图片的源文件；\n",
    "4. $log_n$ 默认表示$log_2{n}$;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 1  \n",
    "\n",
    "> 给定一个已排序的链表的头 `head` ， *删除所有重复的元素，使每个元素只出现一次* 。返回 *已排序的链表* 。链表的类如下所示：\n",
    "\n",
    "```python\n",
    "class NodeList:\n",
    "    def __init__(self, val=None, right=None):\n",
    "        self.val   = val\n",
    "        self.right = right\n",
    "```\n",
    "\n",
    "输入是一个数组，你首先需要将数组转化为链表，然后删除链表中的重复元素，再遍历链表元素，以一个数组的形式返回。请设计一个算法解决上述任务，分析算法设计思路，计算时间复杂度, 并基于python编程实现。\n",
    "\n",
    "e.g.  输入：head=[1, 1, 2, 3, 3]   输出：[1, 2, 3]\n",
    "\n",
    "![image-20240502110020439](./fig/hw2q1.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 2  \n",
    "\n",
    "> 下面是一个经典的算法问题：\n",
    ">\n",
    "> - 给定包含n个整数的一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出 **和为目标值** *`target`* 的那 **两个** 整数，并返回它们的**数组下标**。假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。\n",
    ">\n",
    "> 由于要多次查找数组中元素的位置，为了提高查询效率可以使用哈希表来存储数组中的数据，在哈希表中查询一个元素的复杂度为O(1)。 已知python中的字典是使用哈希表实现的，即使用`dict[key]`查询对应的value时间复杂度为O(1), python提供了查询字典是否包含某个key的功能：`key in dict`，时间复杂度也是O(1)\n",
    "\n",
    "请根据上面信息，设计一个时间复杂度为O(n) 的算法，解决上述算法问题\n",
    "\n",
    "e.g.   \n",
    "\n",
    "输入：nums=[2,7,11,15], target=9， 输出：[0，1]\n",
    "\n",
    "输入：nums=[3,2,4], target=6, 输出：[1,2]\n",
    "\n",
    "输入：nums=[3,3], target=6,  输出：[0,1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is: O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 3:   \n",
    "\n",
    "> 栈是一种常用的数据结构，编译器中通常使用栈来实现表达式求值。\n",
    ">\n",
    "> 以表达式 $3+5 \\times 8-6$​ 为例。编译器使用两个栈来完成运算，即一个栈保持操作数，另一个栈保存运算符。\n",
    ">\n",
    "> 1. 从左向右遍历表达式，遇到数字就压入操作数栈；\n",
    ">\n",
    "> 2. 遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。\n",
    ">\n",
    "> 下图是 $3+5 \\times 8-6$  这个表达式的计算过程：\n",
    "\n",
    "![figure](./fig/hw2q3.png)\n",
    "\n",
    "根据上述原理，请设计一个算法完成表达式的运算，当输入为表达式字符串，返回对应的计算结果。分析算法设计思路，计算时间复杂度，并基于python编程实现\n",
    "\n",
    "**note：**\n",
    "\n",
    "1. 假设输入的表达式只会出现加（“+”），减 “-”， 乘“*”，除 “/” 四个运算符, 表达式中只会出现正整数\n",
    "2. python中` str.isdigit()`函数可以判断字符串str是否为数字，\n",
    "\n",
    "\n",
    "\n",
    "e.g. :\n",
    "---\n",
    "\n",
    "1. 输入：“$3+5 * 8 -6$”   输出：37\n",
    "\n",
    "2. 输入：“$34+13*9 + 44-12/3$”  输出：191"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 4:  \n",
    "\n",
    "> 星球碰撞问题：现有n个星球，在同一条直线上运行，如数组A所示，元素的绝对值表示星球的质量，负数表示星球自右向左运动，正数表示星球自左向右运动，当两个星球相撞的时候，质量小的会消失，大的保持不变，**质量相同的两个星球碰撞后自右向左运动的星球消失，自左向右的星球保持不变**，假设所有星球的速度大小相同。\n",
    ">\n",
    "> $ A=[23,-8, 9, -3, -7, 9, -23, 22] $\n",
    "\n",
    "请设计一个算法模拟星球的运行情况，输出最终的星球存续情况（输出一个数组），分析算法设计思路，计算时间复杂度，并基于python编程实现。\n",
    "\n",
    "e.g.\n",
    "---\n",
    "1.  输入： A=[-3,-6,2,8, 5,-8,9,-2,1]， 输出：[-3, -6, 2, 8, 9, 1]\n",
    "\n",
    "2. 输入：A=[23,-8, 9, -3, -7, 9, -23, 22], 输出：[23, 22]\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 5 \n",
    "\n",
    "> 给定一个无序数组nums=[9,-3,-10,0,9,7,33]，请建立一个二叉搜索树存储数组中的所有元素，之后删除二叉树中的元素“0”，再使用中序遍历输出二叉搜索树中的所有元素。\n",
    "\n",
    "使用python编程完成上述任务，并计算时间复杂度\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 6  \n",
    "\n",
    "> 给定一个包含大写字母和小写字母的字符串 s ，返回 字符串包含的 **最长的回文子串的长度** 。请注意 区分大小写 。比如 \"Aa\" 不能当做一个回文字符串。\n",
    ">\n",
    "\n",
    "请设计一个算法解决上述问题，只需要输出最长回文子串的长度，分析算法设计思路，计算时间复杂度，并基于python编程实现\n",
    "\n",
    "e.g. 输入： s=\"adccaccd\"，  输出：7。 最长回文子串为：\"dccaccd\", 长度为7\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is:\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 7 \n",
    "\n",
    "> 沿一条长河流分散着n座房子。你可以把这条河想象成一条轴，房子是由它们在这条轴上的坐标按顺序排列的。你的公司想在河边的特定地点设置手机基站，这样每户人家都在距离基站4公里的范围内。输入可以看作为一个升序数组，数组元素的取值为大于等于0的正整数，你需要输出最小基站的数目，基站的位置。\n",
    "\n",
    "1. 给出一个时间复杂度为$O(n$) 的算法，使所使用的基站数量最小化，分析算法设计思路，使用python编程实现\n",
    "2. 证明1.中算法产生了最优解决方案。\n",
    "\n",
    "e.g. \n",
    "\n",
    "输入： [1, 5, 12, 33, 34,35]  输出：基站数目为3， 基站位置为[1，12，33]\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 8  \n",
    "\n",
    "> 给定由n个正整数组成的一个集合$S = \\{a_1, a_2，···，a_n\\}$和一个正整数W，设计一个算法确定是否存在S的一个子集 $K \\subseteq S$, 使K中所有数之和为 $W$, 如果存在返回“True”，否则返回“False”\n",
    "\n",
    "请设计一个时间复杂度为$O(nW)$动态规划算法，解决上述问题，分析算法的设计思路，并且基于python编程实现（不需要输出子集）。\n",
    "\n",
    "e.g. \n",
    "\n",
    "输入：S = {1,4,7,3,5}， W = 11，输出：True。   因为K可以是{4,7}。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is: O(nW)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "## 问题 9 \n",
    "\n",
    "> 给定一个n个物品的集合。物体的重量为$w_1, w_2，…、w_n$，物品的价值分别是$v_1、v_2、…v_n$。给你**两个**重量为 $c$ 的背包。如果你带了一个东西，它可以放在一个背包里，也可以放在另一个背包里，但不能同时放在两个背包里。所有权重和价值都是正整数。\n",
    "\n",
    "1. 设计一个时间复杂度为 $O(nc^2)$ 的动态规划算法，确定可以放入两个背包的物体的最大价值。分析算法设计思路，并基于python编程实现\n",
    "2. \\* 修改1中的算法，输出每个背包的内容（物品对应下标）。\n",
    "\n",
    "e.g.: \n",
    "\n",
    "输入 V=[1,3,2,5,8,7], W=[1,3,2,5,8,7], c=7, 输出：最大价值=14，背包装的物品为：[6] [4，3] （同一个背包中物品装入顺序对结果无影响）  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is: O(nc^2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题 10 \n",
    "\n",
    "> 给定两个字符串 $x[1..n]$ 和 $y[1..m]$，我们想通过以下操作将 $x$ 变换为 $y$ :\n",
    ">\n",
    "> **插入**：在 $x$ 中插入一个字符(在任何位置)；**删除**：从 $x$ 中删除一个字符(在任何位置)； **替换**：用另一个字符替换 $x$ 中的一个字符。\n",
    ">\n",
    "> 例如: $x = abcd$, $y = bcfe$，\n",
    ">\n",
    "> - 将 $x$ 转换为 $y$ 的一种可能方法是：1. 删除 $x$ 开头的 $a$, $x$变成 $bcd$； 2. 将 $x$ 中的字符 $d$ 替换为字符 $f$。$x$ 变成 $bcf$； 3. 在 $x$ 的末尾插入字符 $e$。$x$ 变成 $bcfe$。\n",
    ">\n",
    "> - 另一种可能的方法：1. 删除 $x$ 开头的 $a$,  $x$ 变成 $bcd$； 2. 在 $x$ 中字符 $d$ 之前插入字符 $f$。$x$ 变成 $bcfd$。3. 将 $x$ 中的字符 $d$ 替换为字符 $e$。$x$ 变成 $bcfe$。\n",
    "\n",
    "设计一个时间复杂度为 $O(mn)$ 的算法，返回将 $x$ 转换为 $y$ 所需的最少操作次数。分析算法设计思路，并基于python编程实现。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "idea："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add your idea here\n",
    "# your algorithm time complexity is: O(mn)"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
